package com.dyz.swordFingerOffer;

import java.util.ArrayList;

/**
 * @author: daiyizheng
 * @date: 2021/6/5 13:19
 * @description:
 */
public class FindPath34 {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {

        if(root==null){
            return res;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();

        dfs(root, target, arrayList);
        return res;
    }

    public void dfs(TreeNode root, int target, ArrayList<Integer> path){
        if (root == null || target<0){
            return;
        }
        if(root.left==null && root.right==null){
            if(target == root.val){
                path.add(root.val);
                res.add(path);
            }
            return;
        }

        path.add(root.val);
        //进行路径拷贝
        ArrayList<Integer> pathCopy = (ArrayList<Integer>)path.clone();
        dfs(root.left, target-root.val, path);
        dfs(root.right, target-root.val, pathCopy);
        return;
    }
}
